import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 47. 全排列 II
 * https://leetcode-cn.com/problems/permutations-ii/
 */
public class Solutions_47 {
    public static void main(String[] args) {
//        int[] nums = {1, 1, 2};  // output: {{1, 1, 2}, {1, 2, 1}, {2, 1, 1}}
        int[] nums = {1, 3, 2};  // output: {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}

        List<List<Integer>> result = permuteUnique(nums);
        System.out.println(result);
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 空值判断与长度小于 1 的判断
        if (nums == null || nums.length < 1) {
            return res;
        }
        int len = nums.length;

        List<Integer> list = new ArrayList<>();
        // 排序，方便去重操作
        Arrays.sort(nums);
        // mark[2] = true：标记 nums[2] 元素已经添加到列表中（即回溯中）
        boolean[] mark = new boolean[len];
        permuteUnique(nums, res, list, len, mark);
        return res;
    }

    public static void permuteUnique(int[] nums, List<List<Integer>> res,
                                     List<Integer> list, int len, boolean[] mark) {
        // 结束条件
        if (list.size() == len) {
            // 添加结果集并返回
            res.add(new ArrayList<>(list));
        }
        // 每次递归进入时，都从第一个元素开始遍历，保证每个元素都会扫描到
        for (int i = 0; i < len; i++) {
            if (mark[i]) {
                // 已经在列表中则不使用
                continue;
            }
            // 若当前遍历字符与前一字符相同，且前一字符标记为 false时，跳过当前字符，否则会出现重复结果
            if (i > 0 && nums[i] == nums[i - 1] && !mark[i - 1]) {
                // 以 {1, 1, 2} 为例
                // 第二个 1 不能作为列表的开头使用，因为前面相同的 1 已经回溯过一次，再用就是重复
                // 故而判断条件设置为这种情况，第二个 1 作为开头时，第一个 1 的标记一定是 false
                continue;
            }
            // 当前元素若可以使用，则添加到列表中，并将当前元素标记为已使用
            list.add(nums[i]);
            mark[i] = true;
            // 添加元素后，再次递归
            permuteUnique(nums, res, list, len, mark);
            // 递归完成后，移除最后添加的元素，同时还原状态为未使用
            list.remove(list.size() - 1);
            mark[i] = false;
        }
    }
}
